// https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-ii/description

class Solution {
public:
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    // 法一：贪心 O(N)
    int maxProfit(vector<int>& prices) {
        int buy = INT_MAX;
        int profit = 0;
        for (int i = 0; i < prices.size(); ++i) {
            buy = min(prices[i], buy);
            if (prices[i] > buy) {
                //这里不一定要卖，只不过先存起来，下一次比较，有更高的就更新
                profit += prices[i] - buy;
                buy = prices[i];
            }
        }
        return profit;
    }
    // 简化
    int maxProfit(vector<int> &prices) {
        int profit = 0;
        for (int i = 1; i < prices.size(); ++i)
        {
            if (prices[i] > prices[i - 1])
                profit += prices[i] - prices[i - 1];
        }
        return profit;
    }

    // 法二：dp
    int maxProfit(vector<int> &prices) {
        if (prices.empty()) return 0;
        vector<int> res(prices.size(), 0);
        res[0] = 0;
        for (int i = 1; i < prices.size(); ++i) {
            res[i] = max(res[i - 1], res[i - 1] + prices[i] - prices[i - 1]);
        }
        return res.back();
    }

    // 通用dp
    int maxProfit(vector<int>& prices) {
        int n = prices.size(); // 0-不持有 1-持有
        vector<vector<int>> rec(n, vector<int>(2));
        rec[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            rec[i][0] = max(rec[i - 1][0], rec[i - 1][1] + prices[i]);
            rec[i][1] = max(rec[i - 1][0] - prices[i], rec[i - 1][1]);
        }
        return max(rec[n - 1][0], rec[n - 1][1]);
    }
};